package trees.tree

import trees.parsers.TreeData

object TreeBuilder {


    def buildTree(treeData:TreeData,immutable:Boolean):AbstractTree = {
        if(immutable){
            val result= buildTreeFromNewickString(treeData.treeString,immutable,treeData.rooted)
            //println("treeList: "+result._2)
            //println("idlist: "+result._3)
            type N=ImmutableNode
            new ImmutableTree(treeData.treeName,treeData.rooted,treeData.weight,new N(result._1, 0,result._2.size,0,result._3.size),result._2,result._3)
        }else{
            val result= buildTreeFromNewickString(treeData.treeString,immutable,treeData.rooted)
            //println("treeList: "+result._2)
            //println("idlist: "+result._3)
            type N=MutableNode
            new MutableTree(treeData.treeName,treeData.rooted,treeData.weight,new N(result._1, 0,result._2.size,0,result._3.size),result._2,result._3)
        }
    }

    def buildImmutableTree(treeData:TreeData):ImmutableTree = buildTree(treeData,true) match{
        case tree:ImmutableTree => tree
        case _ => throw new Error("Did not build an ImmutableTree")
    }

    def buildMutableTree(treeData:TreeData):MutableTree = buildTree(treeData,false) match{
        case tree:MutableTree => tree
        case _ => throw new Error("Did not build a MutableTree")
    }


    def buildTreeFromNewickString[N >: AbstractNode] (data: String,immutable:Boolean,rooted:Boolean):(List[AbstractLeaf],List[Int],List[Int]) = {


        def sort(a:(List[AbstractLeaf],List[List[Int]],List[List[Int]])):(List[AbstractLeaf],List[List[Int]],List[List[Int]]) = {
            def sort(b:List[AbstractLeaf]):List[Int]={
                //returns a list with the ordered indicies
                b.indices.zip(b.map(_.getMinId)).sort(_._2<_._2).map(_._1)
            }
            val sortedIndices=sort(a._1)
            (sortedIndices.map(a._1(_)), sortedIndices.map(a._2(_)), sortedIndices.map(a._3(_)))
        }



        def build(tokens: List[String],startTree:Int,startId:Int):(List[AbstractLeaf],List[List[Int]],List[List[Int]]) = {
            if (tokens.size==0){
                (List[AbstractLeaf](),List[List[Int]](),List[List[Int]]())
            }else{
                //println(tokens)
                tokens match {
                    case "(" :: rest =>
                        //creates a new node and identifies the portion within the two matching paranthesis
                        // and makes children of it. The remaining portion becomes siblings
                        //println(rest(0))
                        def keepWhile(a:List[String],p : (String) => Boolean):List[String] = {
                            //keeps all entries until one fullfills the condition
                            if(a.size>0){
                                if( p(a(0)) ){
                                    List[String]()
                                }else{
                                    a(0) :: keepWhile(a.tail,p)
                                }
                            }else{
                                List[String]()
                            }
                        }
                        //find start and end values
                        val node=sort(build(keepWhile(rest.tail,_==rest(0)),startTree+1,startId))
                        val tree= IdFactory.getID("(") :: node._2.foldLeft(List[Int]())(_:::_) ::: List(IdFactory.getID(")"))
                        val ids=node._3.foldLeft(List[Int]())(_:::_)
                        val result= build(rest.tail.dropWhile(_!=rest(0)).tail,startTree+ tree.size,startId+ids.size)
                        if(immutable){
                            (new ImmutableNode(node._1,startTree,startTree+tree.size,startId,startId+ids.size) :: result._1,tree::result._2 ,ids::result._3)
                        }else{
                            (new MutableNode(node._1,startTree,startTree+tree.size,startId,startId+ids.size) :: result._1,tree::result._2 ,ids::result._3)
                        }
                    case "," :: tail =>
                        build(tail,startTree,startId)
                    case ";" :: tail =>
                        (List[AbstractLeaf](),List[List[Int]](),List[List[Int]]())
                    case ")" :: ":" :: bl :: tail =>
                        //handle branchlengths
                        build(tail,startTree,startId)
                    case ")" :: tail =>
                        build(tail,startTree,startId)
                    case a :: ":" :: bl :: tail =>
                        //handle branchlengths
                        val result= build(tail,startTree+1,startId+1)
                        (new Leaf(IdFactory.getID(a)) :: result._1, List[Int]((IdFactory.getID(a))) :: result._2, List[Int]((IdFactory.getID(a))) :: result._3)
                    case a :: tail if (tail.size>0)=>
                        val result= build(tail,startTree+1,startId+1)
                        (new Leaf(IdFactory.getID(a)) :: result._1, List[Int]((IdFactory.getID(a))) :: result._2, List[Int]((IdFactory.getID(a))) :: result._3)
                    case a if( a.size==1) =>
                        (List[AbstractLeaf](new Leaf(IdFactory.getID(a(0)))), List[List[Int]](List[Int](IdFactory.getID(a(0)))), List[List[Int]](List[Int](IdFactory.getID(a(0)))))
                    case a =>
                        println("Strange token: "+a)
                        (List[AbstractLeaf](),List[List[Int]](),List[List[Int]]())
                }
            }
        }
        //val tokens= tokenifier(data,0)
        //println (tokens)
        //if (rooted){

        def clean(a:String):String ={
            a.substring(a.indexOf('(')+1,a.lastIndexOf(')'))+";"
        }
        if (rooted){
            val result=sort(build(tokenifier(clean(data),0),2,1))
            val tree= IdFactory.getID("(")::IdFactory.getID("root") :: result._2.foldLeft(List[Int]())(_:::_) ::: List(IdFactory.getID(")"))
            val ids=IdFactory.getID("root")::result._3.foldLeft(List[Int]())(_:::_)
            (new Leaf(IdFactory.getID("root")) :: result._1,tree,ids)
        }else{
            val result=sort(build(tokenifier(clean(data),0),1,0))
            val tree= IdFactory.getID("(") :: result._2.foldLeft(List[Int]())(_:::_) ::: List(IdFactory.getID(")"))
            val ids= result._3.foldLeft(List[Int]())(_:::_)
            (result._1,tree,ids)
        }
    }


    
    private def tokenifier(data:String,level:Int):List[String] = {
        val tokens= """,|:|;""".r
        val labelRegExp="""'.*?'""".r
        //        println(data)
        (data substring(0,1)) match{
            case "'" =>
                //                println("'")
                val pos= data indexOf("'",1)
                if(data.length-1>pos){
                    return (data substring (1,pos)) :: tokenifier(data drop (pos+1),level)
                }else{
                    return List[String](data substring (1,pos))
                }
            case "(" =>
                //                println("(")
                (data substring(0,1)) :: "¤"+(level+1) :: tokenifier(data drop 1,level+1)
            case ")" =>
                //                println(")")
                "¤"+(level) :: (data substring(0,1)) :: tokenifier(data drop 1,level-1)
            case " " =>
                //discards spaces not enclosed by ''
                tokenifier(data drop 1,level)
            case "," =>
                //                println("blä1")
                //must be changed to return all letters until next token
                if (data.length == 1 ){
                    return List[String](data substring(0,1))
                }else{
                    return (data substring(0,1)) :: tokenifier(data drop 1,level)
                }
            case ":" =>
                //                println("blä2")
                //must be changed to return all letters until next token
                if (data.length == 1 ){
                    return List[String](data substring(0,1))
                }else{
                    return (data substring(0,1)) :: tokenifier(data drop 1,level)
                }
            case ";" =>
                //                println("blä3")
                //must be changed to return all letters until next token
                if (data.length == 1 ){
                    return List[String](data substring(0,1))
                }else{
                    return (data substring(0,1)) :: tokenifier(data drop 1,level)
                }
            case _ if(data.length>0) =>
                def endOfToken(data:String):Int = {
                    //fulhack
                    var i= -1
                    var t=0
                    while(i== -1){
                        if(data.charAt(t)==':'||data.charAt(t)==','||data.charAt(t)==')'||data.charAt(t)==';'){
                            i=t
                        }
                        t+=1
                    }
                    i
                }
                //                println(data)
                //                println(endOfToken(data))
                (data substring (0,endOfToken(data))) :: tokenifier((data drop endOfToken(data)), level)
            case _ => List[String]()
        }
    }
}
